﻿#pragma once
#include "Index.h"

/**
 * 滑动窗口的最大值.
* https://leetcode.cn/problems/sliding-window-maximum
* 队列 数组 滑动窗口 单调队列 堆
*
* 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
* 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
* 返回 滑动窗口中的最大值 。
*/
namespace SlidingWindowMaximum
{
    class Question
    {
    public:
        virtual std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) = 0;
    };

    class HeapSolution : public Question
    {
    public:
        /**
         * 堆(优先队列)
         * 时间:O(nlogk) 空间:O(k)
         */
        std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) override
        {
            if (nums.empty() || k <= 0)
                return {};
            const int numsSize = nums.size();

            //要返回的结果，滑动窗口内每次的最大值
            std::vector<int> ans;
            //滑动窗口内的大顶堆 val->index
            std::priority_queue<std::pair<int, int>> maxSliding;

            //先加入k个元素组成第一个窗口
            for (int i = 0; i < k && i < numsSize; ++i)
                maxSliding.emplace(nums[i], i);

            ans.push_back(maxSliding.top().first);
            //只能组成至多一个窗口时直接返回结果
            if (numsSize <= k)
                return ans;

            //开始滑动窗口
            for (int left = 1; left <= numsSize - k; ++left)
            {
                const int right = left + k - 1;
                //右边界扩展
                maxSliding.emplace(nums[right], right);

                //左边界收缩
                while (maxSliding.top().second < left)
                    maxSliding.pop();

                //此时窗口的最大值在队列头，收入到结果中
                ans.push_back(maxSliding.top().first);
            }
            return ans;
        }
    };

    class MonotonicQueue : public Question
    {
    public:
        /**
         * 单调队列
         * 时间:O(n) 空间:O(k)
         */
        std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) override
        {
            if (nums.empty() || k <= 0)
                return {};
            const int numsSize = nums.size();

            //要返回的结果，滑动窗口内每次的最大值
            std::vector<int> ans;
            //双端队列，存储在滑动窗口内的最大值的索引。从队列头到队列尾部对应的元素值从大到小
            std::deque<int> maxSliding;

            //先加入k个元素组成第一个窗口
            for (int i = 0; i < k && i < numsSize; ++i)
            {
                //nums[i]为新加入滑动窗口的元素，不大于nums[i]的元素从队列中弹出
                while (!maxSliding.empty() && nums[i] >= nums[maxSliding.back()])
                    maxSliding.pop_back();

                maxSliding.push_back(i);
            }

            ans.push_back(nums[maxSliding.front()]);
            //只能组成至多一个窗口时直接返回结果
            if (numsSize <= k)
                return ans;

            //开始滑动窗口
            for (int left = 1; left <= numsSize - k; ++left)
            {
                const int right = left + k - 1;
                //右边界扩展
                while (!maxSliding.empty() && nums[right] >= nums[maxSliding.back()])
                    maxSliding.pop_back();
                maxSliding.push_back(right);

                //左边界收缩
                while (maxSliding.front() < left)
                    maxSliding.pop_front();

                //此时窗口的最大值在队列头，收入到结果中
                ans.push_back(nums[maxSliding.front()]);
            }
            return ans;
        }
    };

    class Practice:public Question
    {
    public:
        std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) override
        {
            if(nums.empty() || k<=0)
                return {};
            const int nums_size=nums.size();

            std::deque<int> wnd_dque;
            //首个窗口
            for(int i=0;i<k && i<nums_size;++i)
            {
                if(wnd_dque.empty())
                {
                    wnd_dque.emplace_back(i);
                    continue;
                }

                while(!wnd_dque.empty() && nums[i]> nums[wnd_dque.back()])
                    wnd_dque.pop_back();
                wnd_dque.emplace_back(i);
            }

            std::vector<int> result={nums[wnd_dque.front()]};
            if(nums_size <= k)
                return result;

            //i为滑动窗口的尾元素
            for(int i=k;i<nums_size;++i)
            {
                //新的尾元素加入
                while(!wnd_dque.empty() && nums[i]> nums[wnd_dque.back()])
                    wnd_dque.pop_back();
                wnd_dque.emplace_back(i);

                //旧的头元素移除
                if(wnd_dque.front() <= i-k)
                    wnd_dque.pop_front();

                //当前活动窗口中的最大值
                result.emplace_back(nums[wnd_dque.front()]);
            }

            return result;
        }
    };


    TEST(SlidingWindowMaximumTest, maxSlidingWindow)
    {
        TEST_SOLUTION3(Question,HeapSolution,MonotonicQueue,Practice, &)
        {
            TestingUtil::resetRandSeed();
            std::vector<int> nums = TestingUtil::randRangeInts(100, -500, 500, 0.3f);
            const int numsSize = nums.size();
            //不断增加滑动窗口的大小
            for (int winSize = 1; winSize <= numsSize; ++winSize)
            {
                //固定窗口大小下获得的滑动窗口最大值
                std::vector<int> maxSlidings;
                //窗口开始滑动
                for (int winStart = 0; winStart <= numsSize - winSize; ++winStart)
                {
                    //更新当前窗口内的最大值
                    int maxNum = INT_MIN;
                    for (int i = 0; i < winSize; ++i)
                    {
                        if (nums[winStart + i] > maxNum)
                            maxNum = nums[winStart + i];
                    }
                    maxSlidings.emplace_back(maxNum);
                }

                auto result = solution->maxSlidingWindow(nums, winSize);
                ASSERT_EQ(FormatedUtil::dumpFormated(result), FormatedUtil::dumpFormated(maxSlidings))
                    << "nums=" << FormatedUtil::dumpFormated(nums) << std::endl
                    << "winSize=" << winSize;
            }
        };
    }
}